package 二叉树;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class _102_二叉树的层序遍历 {
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> list = new LinkedList<List<Integer>>();
		if (root == null)
			return list;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		int levelSize = 1;
		List<Integer> innerList = new LinkedList<Integer>();
		while (!queue.isEmpty()) {
			levelSize--;
			TreeNode node = queue.poll();
			innerList.add(node.val);
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
			if (levelSize == 0) {
				list.add(innerList);
				innerList = new LinkedList<Integer>();
				levelSize = queue.size();
			}
		}
		return list;
	}
}
